package org.aplombh.java.awcing.basic.graph.shortestPath.spfa;

import org.aplombh.java.utils.Queue;

import java.util.Arrays;
import java.util.Scanner;

/**
 *给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
 *
 * 请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 impossible。
 *
 * 数据保证不存在负权回路。
 *
 * 输入格式
 * 第一行包含整数 n 和 m。
 *
 * 接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
 *
 * 输出格式
 * 输出一个整数，表示 1 号点到 n 号点的最短距离。
 *
 * 如果路径不存在，则输出 impossible。
 *
 * 数据范围
 * 1≤n,m≤105,
 * 图中涉及边长绝对值均不超过 10000。
 *
 * 输入样例：
 * 3 3
 * 1 2 5
 * 2 3 -3
 * 1 3 4
 * 输出样例：
 * 2
 */
public class Spfa_851 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        Spfa spfa = new Spfa(n);
        while (m-- != 0) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            int c = scanner.nextInt();
            spfa.add(a, b, c);
        }

        System.out.println(spfa.spfa());
    }
}

class Spfa {
    public static final int N = 10010;
    int[] h, w, e, ne; // 存储图 Store the graph
    int[] dist = new int[N]; // 到某点的最短距离 The distance to some point
    boolean[] st = new boolean[N]; // 是否在队列中
    int n, idx;

    Spfa(int n) {
        init(n);
    }

    void init(int n) {
        this.n = n;
        // 初始化 initialize
        h = new int[N];
        w = new int[N];
        e = new int[N];
        ne = new int[N];
        Arrays.fill(h, -1);
        Arrays.fill(dist, 1 << 30);
        dist[1] = 0;
    }

    void add(int a, int b, int c) {
        w[idx] = c;
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    public int spfa() {
        // 新增队列存储改动的点 Add a queue to store the changed points
        Queue<Integer> q = new Queue<>();
        // 入队 enqueue
        q.push(1);
        // 标识该点进入了队列
        st[1] = true;
        while (q.size() != 0) {
            // 出队 dequque
            int t = q.pop();
            st[t] = false;
            // 遍历邻接表 traversing adjacency List
            for (int i = h[t]; i != -1; i = ne[i]) {
                int j = e[i];
                // 如果先到t再到i比之前的距离短，更新当前距离 If the distance from t to i is shorter than the previous distance,update the current distance
                if (dist[j] > dist[t] + w[i]) {
                    dist[j] = dist[t] + w[i];
                    // 如果该点被更新了距离，并且不在队列中 If the point has been updated distance and is not in the queue.
                    if (!st[j]) {
                        // 入队
                        q.push(j);
                        // 标识该点进入了队列
                        st[j] = true;
                    }
                }
            }
        }
        if (dist[n] == 1 << 30) return -1;
        return dist[n];
    }
}